/*
 * BinarySearchTree.h
 * The implementation of a typical binary search tree.
 *  Created on: 2013-1-7
 *      Author: EthanHuang
 */

#ifndef BINARYSEARCHTREE_H_
#define BINARYSEARCHTREE_H_
#include "BinaryNode.h"
#ifndef NULL
#ifdef  __cplusplus
#define NULL    0
#endif
#endif

template<typename ComparableType> class BinarySearchTree
{
public:
	BinarySearchTree();
	BinarySearchTree(const BinarySearchTree& rhs);
	~BinarySearchTree();

	const ComparableType& findMax() const;
	const ComparableType& findMin() const;
	bool contains(const ComparableType& x) const;
	bool isEmpty() const;
	void printTree() const;

	//Delete all BinaryNode that in the BinarySearchTree
	void makeEmpty();
	void insert(const ComparableType& x);
	void remove(const ComparableType& x);
	//make a clone of a BinarySearchTree
	const BinarySearchTree& operator=(const BinarySearchTree& tree);

private:

	//
	struct BinaryNode
	{
		BinaryNode(const ComparableType& elm, BinaryNode* lt, BinaryNode* rt) :
				elm(elm), left(lt), right(rt)
		{
		}
		~BinaryNode()
		{
			left = right = NULL;
		}
		//The actual BinaryNode should hold a element that inherit Comparable
		//interface
		ComparableType elm;
		BinaryNode *left;
		BinaryNode *right;
	};

	//Note: the reference to the pointer of a tree node, makes it easy to
	//modify the tree
	BinaryNode* _root;
	void _insert(const ComparableType& x, BinaryNode* & tree) const;
	void _remove(const ComparableType& x, BinaryNode* & tree) const;
	BinaryNode* _findMax(BinaryNode* x) const;
	BinaryNode* _findMin(BinaryNode* x) const;
	bool _contains(const ComparableType& x, BinaryNode* t) const;
	void _makeEmpty(BinaryNode* node);
	void _printTree(BinaryNode* node) const
	{
	}
	BinaryNode* clone(BinaryNode* node) const;

};

template<typename ComparableType>
inline BinarySearchTree<ComparableType>::BinarySearchTree() :
		_root(NULL)
{
}

template<typename ComparableType>
inline BinarySearchTree<ComparableType>::BinarySearchTree(
		const BinarySearchTree& rhs)
{
	//TODO: create and swap method to clone a tree
}

template<typename ComparableType>
inline BinarySearchTree<ComparableType>::~BinarySearchTree()
{
	makeEmpty();
}

template<typename ComparableType>
inline const ComparableType& BinarySearchTree<ComparableType>::findMax() const
{
	return _findMax(_root)->elm;
}

template<typename ComparableType>
inline const ComparableType& BinarySearchTree<ComparableType>::findMin() const
{
	return _findMin(_root)->elm;
}

template<typename ComparableType>
inline bool BinarySearchTree<ComparableType>::contains(
		const ComparableType& x) const
{
	return _contains(x, _root);
}

template<typename ComparableType>
inline bool BinarySearchTree<ComparableType>::isEmpty() const
{
	return this->_root = NULL ? true : false;
}

template<typename ComparableType>
inline void BinarySearchTree<ComparableType>::printTree() const
{
	_printTree(_root);
}

template<typename ComparableType>
inline void BinarySearchTree<ComparableType>::makeEmpty()
{
	_makeEmpty(_root);
}

template<typename ComparableType>
inline void BinarySearchTree<ComparableType>::insert(const ComparableType& x)
{

}

template<typename ComparableType>
inline void BinarySearchTree<ComparableType>::remove(const ComparableType& x)
{
}

template<typename ComparableType>
inline const BinarySearchTree& BinarySearchTree<ComparableType>::operator =(
		const BinarySearchTree& tree)
{
}

#endif /* BINARYSEARCHTREE_H_ */
